# 111. 二叉树的最小深度
# 给定一个二叉树，找出其最小深度。
# 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
# 说明：叶子节点是指没有子节点的节点。
#
# 示例 1：
# 输入：root = [3,9,20,null,null,15,7]
# 输出：2
#
# 示例 2：
# 输入：root = [2,null,3,null,4,null,5,null,6]
# 输出：5


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def minDepth(self, root):
        # 1.确定递归的参数和返回值
        def getdepth(root):
            # 2.终止条件
            if not root:
                return 0
            # 3.处理逻辑
            leftd = getdepth(root.left)
            rightd = getdepth(root.right)
            if root.left == None and root.right != None:
                return 1 + leftd
            if root.left != None and root.right == None:
                return 1 + rightd
            if root.left != None and root.right != None:
                return 1 + max(leftd,rightd)
        return getdepth(root)
    # 这里是上午写的迭代
    def minDepth2(self, root):
        res = 0
        if not root:
            return res
        from collections import deque
        que = deque()
        que.append(root)
        depth = 0
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
                if not node.left and not node.right: # 当左节点和右节点都没有的时候，就是最小深度了
                    return depth + 1
            depth += 1
        return depth



if __name__ == '__main__':
    # a31 = TreeNode(15)
    # a32 = TreeNode(7)
    # a21 = TreeNode(9)
    # a22 = TreeNode(20,a31,a32)
    # a11 = TreeNode(3,a21,5a22)
    # tmp = Solution()
    # res = tmp.minDepth(root=a11)
    # print(res)

    a5 = TreeNode(6)
    a4 = TreeNode(5,right=a5)
    a3 = TreeNode(4,right=a4)
    a2 = TreeNode(3,right=a3)
    a1 = TreeNode(2,right=a2)
    tmp = Solution()
    res = tmp.minDepth2(a1)
    print(res)
